import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.findAnagrams("cbaebabacd", "abc"));
        System.out.println(s.findAnagrams("abab", "ab"));
    }
}


//官方题解评论，变长窗口
class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> ans = new ArrayList<>();

        char[] left = new char['z' + 1];
        for(int i = 0; i < p.length(); i++){
            left[p.charAt(i)]++;
        }
        int l = 0, r = 0;
        while(r < s.length()){
            if(left[s.charAt(r)] > 0){
                left[s.charAt(r)]--;
                r++;
                if(r - l == p.length()){
                    ans.add(l);
                }
            }
            else{
                left[s.charAt(l)]++;
                l++;
            }
        }
        return ans;
    }
}

//滑动窗口
class Solution1 {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> ans = new ArrayList<>();
        if(s.length() < p.length()){
            return ans;
        }

        Map<Character, Integer> differ = new HashMap<>();
        for(int i = 0; i < p.length(); i++){
            char c = p.charAt(i);
            differ.put(c, differ.getOrDefault(c, 0) - 1);

        }
        for(int i = 0; i < p.length(); i++){
            char c = s.charAt(i);
            differ.put(c, differ.getOrDefault(c, 0) + 1);
            if(differ.get(c) == 0){
                differ.remove(c);
            }
        }
        if(differ.size() == 0){
            ans.add(0);
        }

        for(int i = 1; i + p.length() <= s.length(); i++){

            char head = s.charAt(i + p.length() - 1);
            differ.put(head, differ.getOrDefault(head, 0) + 1);
            if(differ.get(head) == 0){
                differ.remove(head);
            }

            char left = s.charAt(i - 1);
            differ.put(left, differ.getOrDefault(left, 0) - 1);
            if(differ.get(left) == 0){
                differ.remove(left);
            }

            if(differ.size() == 0){
                ans.add(i);
            }
        }

        return ans;
    }
}